/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-12-26
 * Time: 20:38
 */

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution4 {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);// 小根堆
        // 放入第一批头结点
        for (ListNode head : lists) {
            if (head != null) {
                queue.offer(head);
            }
        }
        // 合并链表
        ListNode ret = new ListNode(0);
        ListNode cur = ret;// 定义指针
        while (!queue.isEmpty()) {
            ListNode tmp = queue.poll();
            cur.next = tmp;
            cur = cur.next;
            if (tmp.next != null) {
                tmp = tmp.next;
                queue.offer(tmp);
            }

        }
        return ret.next;
    }
}
public class Test4 {
}
